package org.hot100.h239;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wjy
 * @Date: 2022/2/14 17:27
 */
public class Solution {

    public static void main(String[] args) {

        //int[] ints = {1,3,-1,-3,5,3,6,7};
        int[] ints = {7, 2, 4};
        Solution solution = new Solution();
        int[] res = solution.maxSlidingWindow2(ints, 2);
        System.out.println(Arrays.toString(res));

    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k <= 1) {
            return nums;
        }

        int[] res = new int[nums.length - k + 1];
        int temp = k - 1;
        for (int i = temp; i < nums.length; i++) {
            int max = nums[i - temp];
            for (int j = i - temp; j <= i; j++) {
                if (max < nums[j]) {
                    max = nums[j];
                }
            }
            res[i - temp] = max;
        }

        return res;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0 || k == 1) {
            return nums;
        }

        LinkedList<Integer> queue = new LinkedList<>();
        int right = 0, index = 0;
        int[] res = new int[nums.length - k + 1];

        for (; right < nums.length; right++) {

            // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[right]) {
                queue.pollLast();
            }

            // 添加当前值对应的数组下标
            queue.addLast(right);

            // 判断当前队列中队首的值是否有效
            if (queue.peek() <= right - k) {
                queue.poll();
            }

            if (right >= k - 1) {
                res[right - (k - 1)] = nums[queue.peek()];
            }
        }

        return res;
    }

}
